#include <functional>
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string path;
        int len = 2*n;
        function<void(int,int)> dfs = [&](int index,int cnt_left)
        {
            if(index>=len)
            {
                ret.emplace_back(path);
                return;
            }
            //选择放入左括号，或者不选择放入左括号
            if(cnt_left<n)
            {
                //可以放入左括号
                path.push_back('(');
                dfs(index+1,cnt_left+1);
                path.pop_back();
            }
            if(index-cnt_left<cnt_left)
            {
                //右括号的填入数量小于左括号
                path.push_back(')');
                dfs(index+1,cnt_left);
                path.pop_back();
            }
        };
        dfs(0,0);
        return ret;
    }
};